For the design of digital circuits (e.g., on the scale of very large scale integration (VLSI) technology), designers often employ computer-aided techniques. Standard languages such as hardware description languages (HDLs) have been developed to describe digital circuits to aid in the design and simulation of complex digital circuits. Several hardware description languages, such as VHDL and Verilog, have evolved as industry standards. VHDL and Verilog are general-purpose hardware description languages that allow definition of a hardware model at the gate level, the register transfer level (RTL) or the behavioral level using abstract data types. As device technology continues to advance, various product design tools have been developed to adapt HDLs for use with newer devices and design styles.
In designing an integrated circuit with an HDL code, the code is first written and then compiled by an HDL compiler. The HDL source code describes at some level the circuit elements, and the compiler produces an RTL netlist from this compilation. The RTL netlist is typically a technology independent netlist in that it is independent of the technology/architecture of a specific vendor's integrated circuit, such as field programmable gate arrays (FPGA) or an application-specific integrated circuit (ASIC). The RTL netlist corresponds to a schematic representation of circuit elements (as opposed to a behavioral representation). A mapping operation is then performed to convert from the technology independent RTL netlist to a technology specific netlist, which can be used to create circuits in the vendor's technology/architecture. It is well known that FPGA vendors utilize different technology/architecture to implement logic circuits within their integrated circuits. Thus, the technology independent RTL netlist is mapped to create a netlist, which is specific to a particular vendor's technology/architecture.
Before the placement and routing operation, the timing of signals is typically estimated from parameters such as the fanout of a net and the estimated wire lengths (e.g., obtained from route estimation). After placement of components on the chip and routing of wires between components, timing analysis (e.g., timing simulation or static timing analysis) can be performed to accurately determine the signal delays between logic elements.
A slack associated with a connection is the difference between a required time and an arrival time. The arrival time of a signal is the time elapsed for a signal to arrive at a certain point. The reference, or time 0.0, is often taken as the arrival time of a clock signal. To calculate the arrival time, delay calculation of all the components in the path will be required. The required time is the latest time at which a signal can arrive without making a clock cycle longer than desired. A positive slack at a node implies that the arrival time at that node may be increased by an amount without affecting the overall delay of the circuit. Conversely, negative slack implies that a path may be too slow, and the path must be sped up (or the reference signal delayed) if the whole circuit is to work at the desired speed.
At a detailed level, FPGA (field programmable gate array) routing architectures exhibit many constraints between routing resources and pin assignments (on logic blocks, RAMs, DSPs, etc.). Such constraints are becoming more common in new architectures as the complexity of logic blocks increases and FPGA architects introduce fast local connections for delay optimization. Increasingly, the current approach of separating placement, pin assignment, and routing is not a viable approach and sacrifices delay and therefore QOR (quality of result). In this case QOR degradation implies a longer clock period or a decrease in placement density.
Routing and Pin Assignment Example
FIG. 1A shows a netlist for a pin assignment and routing example. FIG. 1B shows an implementation where signal l and signal m vie for the use of wires W1 and W2 and pins N(A) and N(B). In this example, possible path assignments for l and m and respective slacks are given in the table as shown in FIG. 1C. As can be seen, signal l can reach the load cell using one of four possible paths a, b, c, d. Similarly, signal m can reach the load cell using one of four possible paths e, f, g, h. The goal is to find a path assignment for each of the signals l and m such that the overall or circuit slack is maximized and the paths satisfy mutual constraints.
The first constraint is completeness, which requires the existence of paths for both l and m:                completeness=(a|b|c|d) & (e|f|g|h)In other words one path of [a, b, c, d] and one path of [e, f, g, h] must be chosen. The second constraint is a lack of conflict between the resource usage of the chosen paths. In other words, only one signal can occupy each of the routing resources W1, W2, and only one signal can occupy each of the pin resources N(A) and N(B). In this case conflict is rigorously defined as        conflict=(a & (e|f|g))|(b & (e|f|h))|(c & (e|g|h))|(d & (f|g|h))        
For example, referring to FIG. 1C, when (a & (e|f|g)) is true, there is a conflict. Since path a occupies wire W1 and pin N(B), if any of the other paths also occupies either wire W1 or pin N(B), then there is a conflict. As can be seen from FIG. 1C, at least one of the paths e, f, and g occupies either wire W1 or pin N(B), which leads to a conflict. Similarly, when one of the (b & (e|f|h)), (c & (e|g|h)), or (d & (f|g|h) combinations is true, there will be a conflict. Several scenarios for assigning signals to paths may exist herein.
Scenario A. Independent greedy assignment of paths. In this scenario a list of signals ordered by estimates of criticality has been constructed. Such estimates, being derived from a previously executed process, are only approximate and do not necessarily correspond to slacks on possible paths. A path is chosen for each signal, beginning with the most critical signal. The path chosen maximizes the slack for that signal (e.g., best slack time). Once a path has been chosen for a signal, the choice is not revisited. Subsequent assignments of signals must “live with” the choices remaining to them, i.e. be assigned a path which does not create a conflict with previously assigned signals. This type of assignment is thus a greedy assignment.
Referring back to FIG. 1C, in this example, if signal l has been deemed most critical, we would find a path that maximizes its slack. There are two path choices that give the maximum slack (−0.4) for l:                Assigning l to c gives this maximum slack and, in order to prevent a conflict, requires assigning m to f. The resulting overall slack is then determined by this assignment and is −0.8.        Assigning l to d gives the same maximum slack and, in order to prevent a conflict, requires assigning m to e. This gives an overall slack of −0.6.        
If, on the other hand, signal m has been deemed to be the most critical, path h maximizes its slack. This requires that signal l uses path a, which results in an overall slack of −1.0. Thus the overall slack is dependent upon the ordering in which signals are assigned slacks.
Scenario B. Pin assignment followed by routing. In this approach, pins are assigned in a mutually-exclusive manner and followed by routing (i.e. wire assignments). One implementation is:                Construct a signal ordering based upon some (unspecified) measure of criticality. Assign pins greedily, giving the most critical signals the pins with the most slack. The idea here is to give the most critical signals the best choice of pins.        Route signals to their selected pins using the wire choices available. Any algorithm for routing may be used, such as, for example, the negotiated congestion heuristic. Nearly all routers employ such heuristics and do not give optimal solutions.        
Upon examination of FIG. 1C, there are two cases that must be considered. If l is the most critical signal of l and m, then we could assign l to either N(A) or N(B), as they both have the same slack (−0.4). If we chose N(A), m would be assigned to N(B). The best that the router can do with this pin assignment is to assign l to d and m to e, resulting in a slack of −0.6. There is no guarantee that the router will find this assignment, as routers employ heuristics, which are not guaranteed to find optimal solutions. If we chose to assign l to N(B), m must be assigned to N(A) and the best the router can do with this pin assignment is to assign l to c and m to f, resulting in a slack of −0.8.
If m is the most critical signal we must assign it to N(A), and l must be assigned to N(B). The best the router could do is assign m to f and l to c, giving a slack of −0.8. Again note that the router may not be able to find this assignment and may find another assignment with a worse slack.
Scenario C. Exhaustive path assignment. This method compares all combinations of path assignments for each signal and selects a combination with the best overall slack. In this case, there are (4 paths*4 paths) or 16 combinations. For larger numbers of signals and paths, this method is clearly infeasible. Here, the best assignment (best overall slack) employs paths d and e, giving an overall slack of −0.6.